SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In `F33f`_`[coding theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Coding_theory]`_`f, a `!linear code`! is an `F33f`_`[error-correcting code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Error-correcting_code]`_`f for which any `F33f`_`[linear combination`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_combination]`_`f of `F33f`_`[codewords`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Code_word_(communication)]`_`f is also a codeword. Linear codes are traditionally partitioned into `F33f`_`[block codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Block_code]`_`f and `F33f`_`[convolutional codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Convolutional_code]`_`f, although `F33f`_`[turbo codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Turbo_code]`_`f can be seen as a hybrid of these two types.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. `F33f`_`[syndrome decoding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Syndrome_decoding]`_`f).

Linear codes are used in `F33f`_`[forward error correction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Forward_error_correction]`_`f and are applied in methods for transmitting symbols (e.g., `F33f`_`[bits`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bit]`_`f) on a `F33f`_`[communications channel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Communications_channel]`_`f so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent.`:cite-ref-drmackayecc-2-0[`F5bf`_`[2`#cite-note-drmackayecc-2]`_`f] A linear code of length `*n`* transmits blocks containing `*n`* symbols. For example, the [7,4,3] `F33f`_`[Hamming code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_code]`_`f is a linear `F33f`_`[binary code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_code]`_`f which represents 4-bit messages using 7-bit codewords. Two distinct codewords differ in at least three bits. As a consequence, up to two errors per codeword can be detected while a single error can be corrected.`:cite-ref-cover-and-thomas-3-0[`F5bf`_`[3`#cite-note-cover-and-thomas-3]`_`f] This code contains 24 = 16 codewords.

>>Contents

• `F0af`_`[Definition and parameters`#definition-and-parameters]`_`f

• `F0af`_`[Generator and check matrices`#generator-and-check-matrices]`_`f

• `F0af`_`[Example: Hamming codes`#example-hamming-codes]`_`f

• `F0af`_`[Example: Hadamard codes`#example-hadamard-codes]`_`f

• `F0af`_`[Nearest neighbor algorithm`#nearest-neighbor-algorithm]`_`f

• `F0af`_`[Popular notation`#popular-notation]`_`f

• `F0af`_`[Singleton bound`#singleton-bound]`_`f

• `F0af`_`[Bonisoli's theorem`#bonisoli-s-theorem]`_`f

• `F0af`_`[Examples`#examples]`_`f

• `F0af`_`[Generalization`#generalization]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Bibliography`#bibliography]`_`f

• `F0af`_`[External links`#external-links]`_`f

-─

>>Definition and parameters

A `!linear code`! of length `*n`* and dimension `*k`* is a `F33f`_`[linear subspace`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_subspace]`_`f `*C`* with `F33f`_`[dimension`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimension_(linear_algebra)]`_`f `*k`* of the `F33f`_`[vector space`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Vector_space]`_`f F q n {\\displaystyle \\mathbb {F} _{q}^{n}} where F q {\\displaystyle \\mathbb {F} _{q}} is the `F33f`_`[finite field`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Finite_field]`_`f with `*q`* elements. Such a code is called a `*q`*-ary code. If `*q`* = 2 or `*q`* = 3, the code is described as a `!binary code`!, or a `!ternary code`! respectively. The vectors in `*C`* are called `*codewords`*. The `!size`! of a code is the number of codewords and equals `*q`*`*k`*.

The `!weight`! of a codeword is the number of its elements that are nonzero and the `!distance`! between two codewords is the `F33f`_`[Hamming distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_distance]`_`f between them, that is, the number of elements in which they differ. The distance `*d`* of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length `*n`*, dimension `*k`*, and distance `*d`* is called an [`*n`*,`*k`*,`*d`*] code (or, more precisely, [ n , k , d ] q {\\displaystyle [n,k,d]_{q}} code).

We want to give F q n {\\displaystyle \\mathbb {F} _{q}^{n}} the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (a `F33f`_`[binary symmetric channel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_symmetric_channel]`_`f). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.

>>Generator and check matrices

As a `F33f`_`[linear subspace`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_subspace]`_`f of F q n {\\displaystyle \\mathbb {F} _{q}^{n}} , the entire code `*C`* (which may be very large) may be represented as the `F33f`_`[span`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Span_(linear_algebra)]`_`f of a set of k {\\displaystyle k} codewords (known as a `F33f`_`[basis`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Basis_(linear_algebra)]`_`f in `F33f`_`[linear algebra`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_algebra]`_`f). These basis codewords are often collated in the rows of a matrix G known as a `!`F33f`_`[generating matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Generator_matrix]`_`f`! for the code `*C`*. When G has the block matrix form G = [ I k ∣ ∣ P ] {\\displaystyle {\\boldsymbol {G}}=[I_{k}\\mid P]} , where I k {\\displaystyle I_{k}} denotes the k × × k {\\displaystyle k\\times k} identity matrix and P is some k × × ( n − − k ) {\\displaystyle k\\times (n-k)} matrix, then we say G is in `!standard form`!.

A matrix `*H`* representing a linear function ϕ ϕ : F q n → → F q n − − k {\\displaystyle \\phi :\\mathbb {F} _{q}^{n}\\to \\mathbb {F} _{q}^{n-k}} whose `F33f`_`[kernel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Kernel_(matrix)]`_`f is `*C`* is called a `!`F33f`_`[check matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Check_matrix]`_`f`! of `*C`* (or sometimes a parity check matrix). Equivalently, `*H`* is a matrix whose `F33f`_`[null space`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Null_space]`_`f is `*C`*. If `*C`* is a code with a generating matrix `*G`* in standard form, G = [ I k ∣ ∣ P ] {\\displaystyle {\\boldsymbol {G}}=[I_{k}\\mid P]} , then H = [ − − P T ∣ ∣ I n − − k ] {\\displaystyle {\\boldsymbol {H}}=[-P^{T}\\mid I_{n-k}]} is a check matrix for C. The code generated by `*H`* is called the `!dual code`! of C. It can be verified that G is a k × × n {\\displaystyle k\\times n} matrix, while H is a ( n − − k ) × × n {\\displaystyle (n-k)\\times n} matrix.

Linearity guarantees that the minimum `F33f`_`[Hamming distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_distance]`_`f `*d`* between a codeword `*c`*0 and any of the other codewords `*c`* ≠ `*c`*0 is independent of `*c`*0. This follows from the property that the difference `*c`* − `*c`*0 of two codewords in `*C`* is also a codeword (i.e., an `F33f`_`[element`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Element_(mathematics)]`_`f of the subspace `*C`*), and the property that `*d`*(`*c`*, c0) = `*d`*(`*c`* − `*c`*0, 0). These properties imply that

min c ∈ ∈ C , c ≠ ≠ c 0 d ( c , c 0 ) = min c ∈ ∈ C , c ≠ ≠ c 0 d ( c − − c 0 , 0 ) = min c ∈ ∈ C , c ≠ ≠ 0 d ( c , 0 ) = d . {\\displaystyle \\min _{c\\in C,\\ c\\neq c_{0}}d(c,c_{0})=\\min _{c\\in C,\\ c\\neq c_{0}}d(c-c_{0},0)=\\min _{c\\in C,\\ c\\neq 0}d(c,0)=d.}

In other words, in order to find out the minimum distance between the codewords of a linear code, one would only need to look at the non-zero codewords. The non-zero codeword with the smallest weight has then the minimum distance to the zero codeword, and hence determines the minimum distance of the code.

The distance `*d`* of a linear code `*C`* also equals the minimum number of linearly dependent columns of the check matrix `*H`*.

`*Proof:`* Because H ⋅ ⋅ c T = 0 {\\displaystyle {\\boldsymbol {H}}\\cdot {\\boldsymbol {c}}^{T}={\\boldsymbol {0}}} , which is equivalent to ∑ ∑ i = 1 n ( c i ⋅ ⋅ H i ) = 0 {\\displaystyle \\sum _{i=1}^{n}(c_{i}\\cdot {\\boldsymbol {H_{i}}})={\\boldsymbol {0}}} , where H i {\\displaystyle {\\boldsymbol {H_{i}}}} is the i t h {\\displaystyle i^{th}} column of H {\\displaystyle {\\boldsymbol {H}}} . Remove those items with c i = 0 {\\displaystyle c_{i}=0} , those H i {\\displaystyle {\\boldsymbol {H_{i}}}} with c i ≠ ≠ 0 {\\displaystyle c_{i}\\neq 0} are linearly dependent. Therefore, d {\\displaystyle d} is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns { H j ∣ ∣ j ∈ ∈ S } {\\displaystyle \\{{\\boldsymbol {H_{j}}}\\mid j\\in S\\}} where S {\\displaystyle S} is the column index set. ∑ ∑ i = 1 n ( c i ⋅ ⋅ H i ) = ∑ ∑ j ∈ ∈ S ( c j ⋅ ⋅ H j ) + ∑ ∑ j ∉ ∉ S ( c j ⋅ ⋅ H j ) = 0 {\\displaystyle \\sum _{i=1}^{n}(c_{i}\\cdot {\\boldsymbol {H_{i}}})=\\sum _{j\\in S}(c_{j}\\cdot {\\boldsymbol {H_{j}}})+\\sum _{j\\notin S}(c_{j}\\cdot {\\boldsymbol {H_{j}}})={\\boldsymbol {0}}} . Now consider the vector c ′ {\\displaystyle {\\boldsymbol {c'}}} such that c j ′ = 0 {\\displaystyle c_{j}'=0} if j ∉ ∉ S {\\displaystyle j\\notin S} . Note c ′ ∈ ∈ C {\\displaystyle {\\boldsymbol {c'}}\\in C} because H ⋅ ⋅ c ′ T = 0 {\\displaystyle {\\boldsymbol {H}}\\cdot {\\boldsymbol {c'}}^{T}={\\boldsymbol {0}}} . Therefore, we have d ≤ ≤ w t ( c ′ ) {\\displaystyle d\\leq wt({\\boldsymbol {c'}})} , which is the minimum number of linearly dependent columns in H {\\displaystyle {\\boldsymbol {H}}} . The claimed property is therefore proven.

>>Example: Hamming codes

As the first class of linear codes developed for error correction purpose, `F33f`_`[Hamming codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_code]`_`f have been widely used in digital communication systems. For any positive integer r ≥ ≥ 2 {\\displaystyle r\\geq 2} , there exists a [ 2 r − − 1 , 2 r − − r − − 1 , 3 ] 2 {\\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}} Hamming code. Since d = 3 {\\displaystyle d=3} , this Hamming code can correct a 1-bit error.

`!Example :`! The linear block code with the following generator matrix and parity check matrix is a [ 7 , 4 , 3 ] 2 {\\displaystyle [7,4,3]_{2}} Hamming code.

G = ( 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 ) , {\\displaystyle {\\boldsymbol {G}}={\\begin{pmatrix}1&0&0&0&1&1&0\\\\0&1&0&0&0&1&1\\\\0&0&1&0&1&1&1\\\\0&0&0&1&1&0&1\\end{pmatrix}},} H = ( 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 ) {\\displaystyle {\\boldsymbol {H}}={\\begin{pmatrix}1&0&1&1&1&0&0\\\\1&1&\\ 1&0&0&1&0\\\\0&1&1&1&0&0&1\\end{pmatrix}}}

>>Example: Hadamard codes

`F33f`_`[Hadamard code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hadamard_code]`_`f is a [ 2 r , r , 2 r − − 1 ] 2 {\\displaystyle [2^{r},r,2^{r-1}]_{2}} linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the i t h {\\displaystyle i^{th}} column is the bits of the binary representation of integer i {\\displaystyle i} , as shown in the following example. Hadamard code has minimum distance 2 r − − 1 {\\displaystyle 2^{r-1}} and therefore can correct 2 r − − 2 − − 1 {\\displaystyle 2^{r-2}-1} errors.

`!Example:`! The linear block code with the following generator matrix is a [ 8 , 3 , 4 ] 2 {\\displaystyle [8,3,4]_{2}} Hadamard code: G H a d = ( 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 ) {\\displaystyle {\\boldsymbol {G}}_{\\mathrm {Had} }={\\begin{pmatrix}0&0&0&0&1&\\ 1&1&1\\\\0&0&1&1&0&0&1&1\\\\0&1&0&1&0&1&0&1\\end{pmatrix}}} .

`F33f`_`[Hadamard code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hadamard_code]`_`f is a special case of `F33f`_`[Reed–Muller code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reed–Muller_code]`_`f. If we take the first column (the all-zero column) out from G H a d {\\displaystyle {\\boldsymbol {G}}_{\\mathrm {Had} }} , we get [ 7 , 3 , 4 ] 2 {\\displaystyle [7,3,4]_{2}} `*simplex code`*, which is the `*dual code `* of Hamming code.

>>Nearest neighbor algorithm

The parameter d is closely related to the error correcting ability of the code. The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A `*received vector`* v in F q n . {\\displaystyle \\mathbb {F} _{q}^{n}.}

Output: A codeword w {\\displaystyle w} in C {\\displaystyle C} closest to v {\\displaystyle v} , if any.

• Starting with t = 0 {\\displaystyle t=0} , repeat the following two steps.

• Enumerate the elements of the ball of (Hamming) radius t {\\displaystyle t} around the received word v {\\displaystyle v} , denoted B t ( v ) {\\displaystyle B_{t}(v)} .

• For each w {\\displaystyle w} in B t ( v ) {\\displaystyle B_{t}(v)} , check if w {\\displaystyle w} in C {\\displaystyle C} . If so, return w {\\displaystyle w} as the solution.

• Increment t {\\displaystyle t} . Fail only when t > ( d − − 1 ) / 2 {\\displaystyle t>(d-1)/2} so enumeration is complete and no solution has been found.

We say that a linear C {\\displaystyle C} is t {\\displaystyle t} -error correcting if there is at most one codeword in B t ( v ) {\\displaystyle B_{t}(v)} , for each v {\\displaystyle v} in F q n {\\displaystyle \\mathbb {F} _{q}^{n}} .

>>Popular notation

`F33f`_`[Codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Code]`_`f in general are often denoted by the letter `*C`*, and a code of length `*n`* and of `F33f`_`[rank`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimension_(linear_algebra)]`_`f `*k`* (i.e., having `*n`* code words in its basis and `*k`* rows in its `*generating matrix`*) is generally referred to as an (`*n`*, `*k`*) code. Linear block codes are frequently denoted as [`*n`*, `*k`*, `*d`*] codes, where `*d`* refers to the code's minimum Hamming distance between any two code words.

(The [`*n`*, `*k`*, `*d`*] notation should not be confused with the (`*n`*, `*M`*, `*d`*) notation used to denote a `*non-linear`* code of length `*n`*, size `*M`* (i.e., having `*M`* code words), and minimum Hamming distance `*d`*.)

>>Singleton bound

`*Lemma`* (`F33f`_`[Singleton bound`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Singleton_bound]`_`f): Every linear [`*n`*,`*k`*,`*d`*] code C satisfies k + d ≤ ≤ n + 1 {\\displaystyle k+d\\leq n+1} .

A code `*C`* whose parameters satisfy `*k`* +`*d`* = `*n`* + 1 is called `!maximum distance separable`! or `!MDS`!. Such codes, when they exist, are in some sense best possible.

If `*C`*1 and `*C`*2 are two codes of length `*n`* and if there is a permutation `*p`* in the `F33f`_`[symmetric group`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Symmetric_group]`_`f `*S`*`*n`* for which (`*c`*1,...,`*c`*`*n`*) in `*C`*1 if and only if (`*c`*`*p`*(1),...,`*c`*`*p`*(`*n`*)) in `*C`*2, then we say `*C`*1 and `*C`*2 are `!permutation equivalent`!. In more generality, if there is an n × × n {\\displaystyle n\\times n} `F33f`_`[monomial matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Monomial_matrix]`_`f M : : F q n → → F q n {\\displaystyle M\\colon \\mathbb {F} _{q}^{n}\\to \\mathbb {F} _{q}^{n}} which sends `*C`*1 isomorphically to `*C`*2 then we say `*C`*1 and `*C`*2 are `!equivalent`!.

`*Lemma`*: Any linear code is permutation equivalent to a code which is in standard form.

>>Bonisoli's theorem

A code is defined to be `!equidistant`! if and only if there exists some constant `*d`* such that the distance between any two of the code's distinct codewords is equal to `*d`*.`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f] In 1984 Arrigo Bonisoli determined the structure of linear one-weight codes over finite fields and proved that every equidistant linear code is a sequence of `F33f`_`[dual`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dual_code]`_`f `F33f`_`[Hamming codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_code]`_`f.`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

>>Examples

Some examples of linear codes include:

• `F33f`_`[Repetition code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Repetition_code]`_`f

• `F33f`_`[Parity code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parity_code]`_`f

• `F33f`_`[Cyclic code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cyclic_code]`_`f

• `F33f`_`[Hamming code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_code]`_`f

• `F33f`_`[Golay code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Golay_code_(disambiguation)]`_`f, both the `F33f`_`[binary`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_Golay_code]`_`f and `F33f`_`[ternary`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ternary_Golay_code]`_`f versions

• `F33f`_`[Polynomial codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polynomial_code]`_`f, of which `F33f`_`[BCH codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=BCH_code]`_`f are an example

• `F33f`_`[Reed–Solomon codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reed–Solomon_error_correction]`_`f

• `F33f`_`[Reed–Muller code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Reed–Muller_code]`_`f

• `F33f`_`[Algebraic geometry code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algebraic_geometry_code]`_`f

• `F33f`_`[Binary Goppa code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_Goppa_code]`_`f

• `F33f`_`[Low-density parity-check codes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Low-density_parity-check_codes]`_`f

• `F33f`_`[Expander code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Expander_code]`_`f

• `F33f`_`[Multidimensional parity-check code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multidimensional_parity-check_code]`_`f

• `F33f`_`[Toric code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Toric_code]`_`f

• `F33f`_`[Turbo code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Turbo_code]`_`f

• `F33f`_`[Locally recoverable code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Locally_recoverable_code]`_`f

>>Generalization

`F33f`_`[Hamming spaces`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_space]`_`f over non-field alphabets have also been considered, especially over `F33f`_`[finite rings`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Finite_ring]`_`f, most notably `F33f`_`[Galois rings`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Galois_ring]`_`f over `F33f`_`[Z4`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Modular_arithmetic]`_`f. This gives rise to `F33f`_`[modules`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Module_(mathematics)]`_`f instead of vector spaces and ring-linear codes (identified with `F33f`_`[submodules`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Submodule]`_`f) instead of linear codes. The typical metric used in this case the `F33f`_`[Lee distance`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lee_distance]`_`f. There exist a `F33f`_`[Gray isometry`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Gray_isometry]`_`f between Z 2 2 m {\\displaystyle \\mathbb {Z} _{2}^{2m}} (i.e. GF(22`*m`*)) with the Hamming distance and Z 4 m {\\displaystyle \\mathbb {Z} _{4}^{m}} (also denoted as GR(4,m)) with the Lee distance; its main attraction is that it establishes a correspondence between some "good" codes that are not linear over Z 2 2 m {\\displaystyle \\mathbb {Z} _{2}^{2m}} as images of ring-linear codes from Z 4 m {\\displaystyle \\mathbb {Z} _{4}^{m}} .`:cite-ref-greferath2009-6-0[`F5bf`_`[6`#cite-note-greferath2009-6]`_`f]`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]`:cite-ref-lint1999-8-0[`F5bf`_`[8`#cite-note-lint1999-8]`_`f]

Some authors have referred to such codes over rings simply as linear codes as well.`:cite-ref-doughertyfacchini2015-9-0[`F5bf`_`[9`#cite-note-doughertyfacchini2015-9]`_`f]

>>See also

• `F33f`_`[Decoding methods`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decoding_methods]`_`f

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefwilliam-e-ryan-and-shu-lin2009`aWilliam E. Ryan and Shu Lin (2009). `*Channel Codes: Classical and Modern`*. Cambridge University Press. p. 4. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-521-84868-8.

`:cite-note-drmackayecc-2`!2.`! `F0af`_`[↑`#cite-ref-drmackayecc-2-0]`_`f `:citerefmackay2003`a`F33f`_`[MacKay, David, J.C.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=David_J.C._MacKay]`_`f (2003). `*Information Theory, Inference, and Learning Algorithms`* (PDF). `F33f`_`[Cambridge University Press`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cambridge_University_Press]`_`f. p. 9. `F33f`_`[Bibcode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bibcode_(identifier)]`_`f:2003itil.book.....M. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 9780521642989. In a `*linear`* block code, the extra N − − K {\\displaystyle N-K} bits are linear functions of the original K {\\displaystyle K} bits; these extra bits are called `*parity-check bits`*`B100`F9d9{{cite book}}`f`b: CS1 maint: multiple names: authors list (link)

`:cite-note-cover-and-thomas-3`!3.`! `F0af`_`[↑`#cite-ref-cover-and-thomas-3-0]`_`f `:citerefthomas-m-cover-and-joy-a-thomas1991`aThomas M. Cover and Joy A. Thomas (1991). `*Elements of Information Theory`*. John Wiley & Sons, Inc. pp. 210–211. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-471-06259-2.

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefetzion-tuviraviv-netanel2013`aEtzion, Tuvi; Raviv, Netanel (2013). "Equidistant codes in the Grassmannian". `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1308.6231 [math.CO].

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `:citerefbonisoli-a-1984`aBonisoli, A. (1984). "Every equidistant linear code is a sequence of dual Hamming codes". `*Ars Combinatoria`*. `!18`!: 181–186.

`:cite-note-greferath2009-6`!6.`! `F0af`_`[↑`#cite-ref-greferath2009-6-0]`_`f `:citerefmarcus-greferath2009`aMarcus Greferath (2009). "An Introduction to Ring-Linear Coding Theory". In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). `*Gröbner Bases, Coding, and Cryptography`*. Springer Science & Business Media. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-540-93806-4.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f "Encyclopedia of Mathematics". `*www.encyclopediaofmath.org`*.

`:cite-note-lint1999-8`!8.`! `F0af`_`[↑`#cite-ref-lint1999-8-0]`_`f `:citerefj-h-van-lint1999`aJ.H. van Lint (1999). `*Introduction to Coding Theory`* (3rd ed.). Springer. Chapter 8: Codes over ℤ4. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-540-64133-9.

`:cite-note-doughertyfacchini2015-9`!9.`! `F0af`_`[↑`#cite-ref-doughertyfacchini2015-9-0]`_`f `:citerefs-t-doughertyj-l-kimp-sole2015`aS.T. Dougherty; J.-L. Kim; P. Sole (2015). "Open Problems in Coding Theory". In Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). `*Noncommutative Rings and Their Applications`*. American Mathematical Soc. p. 80. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-4704-1032-2.

>>>Bibliography

• `:citerefj-f-humphreysm-y-prest2004`aJ. F. Humphreys; M. Y. Prest (2004). `*Numbers, Groups and Codes`* (2nd ed.). Cambridge University Press. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

>>External links

• `*q`*-ary code generator program

• Code Tables: Bounds on the parameters of various types of codes, `*IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]`*. Online, up to date table of the optimal binary codes, includes non-binary codes.

• The database of Z4 codes Online, up to date database of optimal Z4 codes.

`c`F0af`_`[↑ Back to top`#top]`_`f`a